Clover icon

compiler

  1. Project Clover database Mon Jan 2 2023 15:09:37 MST
  2. Package com.google.javascript.jscomp.type

File SemanticReverseAbstractInterpreter.java

 

Coverage histogram

../../../../../img/srcFileCovDistChart9.png
54% of files have more coverage

Code metrics

108
227
28
3
602
460
117
0.52
8.11
9.33
4.18

Classes

Class Line # Actions
SemanticReverseAbstractInterpreter 41 196 97 19
0.937704993.8%
SemanticReverseAbstractInterpreter.RestrictByTrueInstanceOfResultVisitor 503 15 11 8
0.7142857371.4%
SemanticReverseAbstractInterpreter.RestrictByFalseInstanceOfResultVisitor 557 16 9 12
0.660%
 

Contributing tests

This file is covered by 6611 tests. .

Source view

1    /*
2    * Copyright 2007 The Closure Compiler Authors.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10    * Unless required by applicable law or agreed to in writing, software
11    * distributed under the License is distributed on an "AS IS" BASIS,
12    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13    * See the License for the specific language governing permissions and
14    * limitations under the License.
15    */
16   
17    package com.google.javascript.jscomp.type;
18   
19    import static com.google.javascript.rhino.jstype.JSTypeNative.UNKNOWN_TYPE;
20   
21    import com.google.common.base.Function;
22    import com.google.javascript.jscomp.CodingConvention;
23    import com.google.javascript.rhino.Node;
24    import com.google.javascript.rhino.Token;
25    import com.google.javascript.rhino.jstype.FunctionType;
26    import com.google.javascript.rhino.jstype.JSType;
27    import com.google.javascript.rhino.jstype.JSType.TypePair;
28    import com.google.javascript.rhino.jstype.JSTypeNative;
29    import com.google.javascript.rhino.jstype.JSTypeRegistry;
30    import com.google.javascript.rhino.jstype.ObjectType;
31    import com.google.javascript.rhino.jstype.StaticSlot;
32    import com.google.javascript.rhino.jstype.UnionType;
33    import com.google.javascript.rhino.jstype.Visitor;
34   
35    /**
36    * A reverse abstract interpreter using the semantics of the JavaScript
37    * language as a means to reverse interpret computations. This interpreter
38    * expects the parse tree inputs to be typed.
39    *
40    */
 
41    public class SemanticReverseAbstractInterpreter
42    extends ChainableReverseAbstractInterpreter {
43   
44    /**
45    * Merging function for equality between types.
46    */
47    private static final Function<TypePair, TypePair> EQ =
48    new Function<TypePair, TypePair>() {
 
49  180 toggle @Override
50    public TypePair apply(TypePair p) {
51  180 if (p.typeA == null || p.typeB == null) {
52  4 return null;
53    }
54  176 return p.typeA.getTypesUnderEquality(p.typeB);
55    }
56    };
57   
58    /**
59    * Merging function for non-equality between types.
60    */
61    private static final Function<TypePair, TypePair> NE =
62    new Function<TypePair, TypePair>() {
 
63  164 toggle @Override
64    public TypePair apply(TypePair p) {
65  164 if (p.typeA == null || p.typeB == null) {
66  4 return null;
67    }
68  160 return p.typeA.getTypesUnderInequality(p.typeB);
69    }
70    };
71   
72    /**
73    * Merging function for strict equality between types.
74    */
75    private static final
76    Function<TypePair, TypePair> SHEQ =
77    new Function<TypePair, TypePair>() {
 
78  98 toggle @Override
79    public TypePair apply(TypePair p) {
80  98 if (p.typeA == null || p.typeB == null) {
81  3 return null;
82    }
83  95 return p.typeA.getTypesUnderShallowEquality(p.typeB);
84    }
85    };
86   
87    /**
88    * Merging function for strict non-equality between types.
89    */
90    private static final
91    Function<TypePair, TypePair> SHNE =
92    new Function<TypePair, TypePair>() {
 
93  102 toggle @Override
94    public TypePair apply(TypePair p) {
95  102 if (p.typeA == null || p.typeB == null) {
96  3 return null;
97    }
98  99 return p.typeA.getTypesUnderShallowInequality(p.typeB);
99    }
100    };
101   
102    /**
103    * Merging function for inequality comparisons between types.
104    */
105    private final
106    Function<TypePair, TypePair> INEQ =
107    new Function<TypePair, TypePair>() {
 
108  127 toggle @Override
109    public TypePair apply(TypePair p) {
110  127 return new TypePair(
111    getRestrictedWithoutUndefined(p.typeA),
112    getRestrictedWithoutUndefined(p.typeB));
113    }
114    };
115   
116    /**
117    * Creates a semantic reverse abstract interpreter.
118    */
 
119  7206 toggle public SemanticReverseAbstractInterpreter(CodingConvention convention,
120    JSTypeRegistry typeRegistry) {
121  7206 super(convention, typeRegistry);
122    }
123   
 
124  3630 toggle @Override
125    public FlowScope getPreciserScopeKnowingConditionOutcome(Node condition,
126    FlowScope blindScope, boolean outcome) {
127    // Check for the typeof operator.
128  3630 int operatorToken = condition.getType();
129  3630 switch (operatorToken) {
130  446 case Token.EQ:
131  112 case Token.NE:
132  40 case Token.SHEQ:
133  36 case Token.SHNE:
134  154 case Token.CASE:
135  788 Node left;
136  788 Node right;
137  788 if (operatorToken == Token.CASE) {
138  154 left = condition.getParent().getFirstChild(); // the switch condition
139  154 right = condition.getFirstChild();
140    } else {
141  634 left = condition.getFirstChild();
142  634 right = condition.getLastChild();
143    }
144   
145  788 Node typeOfNode = null;
146  788 Node stringNode = null;
147  788 if (left.isTypeOf() && right.isString()) {
148  280 typeOfNode = left;
149  280 stringNode = right;
150  508 } else if (right.isTypeOf() &&
151    left.isString()) {
152  0 typeOfNode = right;
153  0 stringNode = left;
154    }
155  788 if (typeOfNode != null && stringNode != null) {
156  280 Node operandNode = typeOfNode.getFirstChild();
157  280 JSType operandType = getTypeIfRefinable(operandNode, blindScope);
158  280 if (operandType != null) {
159  244 boolean resultEqualsValue = operatorToken == Token.EQ ||
160    operatorToken == Token.SHEQ || operatorToken == Token.CASE;
161  244 if (!outcome) {
162  116 resultEqualsValue = !resultEqualsValue;
163    }
164  244 return caseTypeOf(operandNode, operandType, stringNode.getString(),
165    resultEqualsValue, blindScope);
166    }
167    }
168    }
169  3386 switch (operatorToken) {
170  142 case Token.AND:
171  142 if (outcome) {
172  69 return caseAndOrNotShortCircuiting(condition.getFirstChild(),
173    condition.getLastChild(), blindScope, true);
174    } else {
175  73 return caseAndOrMaybeShortCircuiting(condition.getFirstChild(),
176    condition.getLastChild(), blindScope, true);
177    }
178   
179  44 case Token.OR:
180  44 if (!outcome) {
181  21 return caseAndOrNotShortCircuiting(condition.getFirstChild(),
182    condition.getLastChild(), blindScope, false);
183    } else {
184  23 return caseAndOrMaybeShortCircuiting(condition.getFirstChild(),
185    condition.getLastChild(), blindScope, false);
186    }
187   
188  274 case Token.EQ:
189  274 if (outcome) {
190  146 return caseEquality(condition, blindScope, EQ);
191    } else {
192  128 return caseEquality(condition, blindScope, NE);
193    }
194   
195  70 case Token.NE:
196  70 if (outcome) {
197  36 return caseEquality(condition, blindScope, NE);
198    } else {
199  34 return caseEquality(condition, blindScope, EQ);
200    }
201   
202  40 case Token.SHEQ:
203  40 if (outcome) {
204  19 return caseEquality(condition, blindScope, SHEQ);
205    } else {
206  21 return caseEquality(condition, blindScope, SHNE);
207    }
208   
209  36 case Token.SHNE:
210  36 if (outcome) {
211  19 return caseEquality(condition, blindScope, SHNE);
212    } else {
213  17 return caseEquality(condition, blindScope, SHEQ);
214    }
215   
216  1029 case Token.NAME:
217  279 case Token.GETPROP:
218  1308 return caseNameOrGetProp(condition, blindScope, outcome);
219   
220  23 case Token.ASSIGN:
221  23 return firstPreciserScopeKnowingConditionOutcome(
222    condition.getFirstChild(),
223    firstPreciserScopeKnowingConditionOutcome(
224    condition.getFirstChild().getNext(), blindScope, outcome),
225    outcome);
226   
227  259 case Token.NOT:
228  259 return firstPreciserScopeKnowingConditionOutcome(
229    condition.getFirstChild(), blindScope, !outcome);
230   
231  12 case Token.LE:
232  188 case Token.LT:
233  32 case Token.GE:
234  22 case Token.GT:
235  254 if (outcome) {
236  127 return caseEquality(condition, blindScope, INEQ);
237    }
238  127 break;
239   
240  142 case Token.INSTANCEOF:
241  142 return caseInstanceOf(
242    condition.getFirstChild(), condition.getLastChild(), blindScope,
243    outcome);
244   
245  4 case Token.IN:
246  4 if (outcome && condition.getFirstChild().isString()) {
247  2 return caseIn(condition.getLastChild(),
248    condition.getFirstChild().getString(), blindScope);
249    }
250  2 break;
251   
252  124 case Token.CASE:
253  124 Node left =
254    condition.getParent().getFirstChild(); // the switch condition
255  124 Node right = condition.getFirstChild();
256  124 if (outcome) {
257  62 return caseEquality(left, right, blindScope, SHEQ);
258    } else {
259  62 return caseEquality(left, right, blindScope, SHNE);
260    }
261    }
262  795 return nextPreciserScopeKnowingConditionOutcome(
263    condition, blindScope, outcome);
264    }
265   
 
266  547 toggle private FlowScope caseEquality(Node condition, FlowScope blindScope,
267    Function<TypePair, TypePair> merging) {
268  547 return caseEquality(condition.getFirstChild(), condition.getLastChild(),
269    blindScope, merging);
270    }
271   
 
272  671 toggle private FlowScope caseEquality(Node left, Node right, FlowScope blindScope,
273    Function<TypePair, TypePair> merging) {
274    // left type
275  671 JSType leftType = getTypeIfRefinable(left, blindScope);
276  671 boolean leftIsRefineable;
277  671 if (leftType != null) {
278  546 leftIsRefineable = true;
279    } else {
280  125 leftIsRefineable = false;
281  125 leftType = left.getJSType();
282    }
283   
284    // right type
285  671 JSType rightType = getTypeIfRefinable(right, blindScope);
286  671 boolean rightIsRefineable;
287  671 if (rightType != null) {
288  178 rightIsRefineable = true;
289    } else {
290  493 rightIsRefineable = false;
291  493 rightType = right.getJSType();
292    }
293   
294    // merged types
295  671 TypePair merged = merging.apply(new TypePair(leftType, rightType));
296   
297    // creating new scope
298  671 if (merged != null) {
299  657 return maybeRestrictTwoNames(
300    blindScope,
301  657 left, leftType, leftIsRefineable ? merged.typeA : null,
302  657 right, rightType, rightIsRefineable ? merged.typeB : null);
303    }
304  14 return blindScope;
305    }
306   
 
307  90 toggle private FlowScope caseAndOrNotShortCircuiting(Node left, Node right,
308    FlowScope blindScope, boolean condition) {
309    // left type
310  90 JSType leftType = getTypeIfRefinable(left, blindScope);
311  90 boolean leftIsRefineable;
312  90 if (leftType != null) {
313  48 leftIsRefineable = true;
314    } else {
315  42 leftIsRefineable = false;
316  42 leftType = left.getJSType();
317  42 blindScope = firstPreciserScopeKnowingConditionOutcome(
318    left, blindScope, condition);
319    }
320   
321    // restricting left type
322  90 JSType restrictedLeftType = (leftType == null) ? null :
323    leftType.getRestrictedTypeGivenToBooleanOutcome(condition);
324  90 if (restrictedLeftType == null) {
325  0 return firstPreciserScopeKnowingConditionOutcome(
326    right, blindScope, condition);
327    }
328   
329    // right type
330  90 JSType rightType = getTypeIfRefinable(right, blindScope);
331  90 boolean rightIsRefineable;
332  90 if (rightType != null) {
333  21 rightIsRefineable = true;
334    } else {
335  69 rightIsRefineable = false;
336  69 rightType = right.getJSType();
337  69 blindScope = firstPreciserScopeKnowingConditionOutcome(
338    right, blindScope, condition);
339    }
340   
341  90 if (condition) {
342  69 JSType restrictedRightType = (rightType == null) ? null :
343    rightType.getRestrictedTypeGivenToBooleanOutcome(condition);
344   
345    // creating new scope
346  69 return maybeRestrictTwoNames(
347    blindScope,
348  69 left, leftType, leftIsRefineable ? restrictedLeftType : null,
349  69 right, rightType, rightIsRefineable ? restrictedRightType : null);
350    }
351  21 return blindScope;
352    }
353   
 
354  96 toggle private FlowScope caseAndOrMaybeShortCircuiting(Node left, Node right,
355    FlowScope blindScope, boolean condition) {
356  96 FlowScope leftScope = firstPreciserScopeKnowingConditionOutcome(
357    left, blindScope, !condition);
358  96 StaticSlot<JSType> leftVar = leftScope.findUniqueRefinedSlot(blindScope);
359  96 if (leftVar == null) {
360  50 return blindScope;
361    }
362  46 FlowScope rightScope = firstPreciserScopeKnowingConditionOutcome(
363    left, blindScope, condition);
364  46 rightScope = firstPreciserScopeKnowingConditionOutcome(
365    right, rightScope, !condition);
366  46 StaticSlot<JSType> rightVar = rightScope.findUniqueRefinedSlot(blindScope);
367  46 if (rightVar == null || !leftVar.getName().equals(rightVar.getName())) {
368  11 return blindScope;
369    }
370  35 JSType type = leftVar.getType().getLeastSupertype(rightVar.getType());
371  35 FlowScope informed = blindScope.createChildFlowScope();
372  35 informed.inferSlotType(leftVar.getName(), type);
373  35 return informed;
374    }
375   
376    /**
377    * If the restrictedType differs from the originalType, then we should
378    * branch the current flow scope and create a new flow scope with the name
379    * declared with the new type.
380    *
381    * We try not to create spurious child flow scopes as this makes type
382    * inference slower.
383    *
384    * We also do not want spurious slots around in type inference, because
385    * we use these as a signal for "checked unknown" types. A "checked unknown"
386    * type is a symbol that the programmer has already checked and verified that
387    * it's defined, even if we don't know what it is.
388    *
389    * It is OK to pass non-name nodes into this method, as long as you pass
390    * in {@code null} for a restricted type.
391    */
 
392  1552 toggle private FlowScope maybeRestrictName(
393    FlowScope blindScope, Node node, JSType originalType, JSType restrictedType) {
394  1552 if (restrictedType != null && restrictedType != originalType) {
395  1124 FlowScope informed = blindScope.createChildFlowScope();
396  1124 declareNameInScope(informed, node, restrictedType);
397  1124 return informed;
398    }
399  428 return blindScope;
400    }
401   
402    /**
403    * @see #maybeRestrictName
404    */
 
405  726 toggle private FlowScope maybeRestrictTwoNames(
406    FlowScope blindScope,
407    Node left, JSType originalLeftType, JSType restrictedLeftType,
408    Node right, JSType originalRightType, JSType restrictedRightType) {
409  726 boolean shouldRefineLeft =
410    restrictedLeftType != null && restrictedLeftType != originalLeftType;
411  726 boolean shouldRefineRight =
412    restrictedRightType != null && restrictedRightType != originalRightType;
413  726 if (shouldRefineLeft || shouldRefineRight) {
414  318 FlowScope informed = blindScope.createChildFlowScope();
415  318 if (shouldRefineLeft) {
416  293 declareNameInScope(informed, left, restrictedLeftType);
417    }
418  318 if (shouldRefineRight) {
419  77 declareNameInScope(informed, right, restrictedRightType);
420    }
421  318 return informed;
422    }
423  408 return blindScope;
424    }
425   
 
426  1308 toggle private FlowScope caseNameOrGetProp(Node name, FlowScope blindScope,
427    boolean outcome) {
428  1308 JSType type = getTypeIfRefinable(name, blindScope);
429  1308 if (type != null) {
430  1226 return maybeRestrictName(
431    blindScope, name, type,
432    type.getRestrictedTypeGivenToBooleanOutcome(outcome));
433    }
434  82 return blindScope;
435    }
436   
 
437  244 toggle private FlowScope caseTypeOf(Node node, JSType type, String value,
438    boolean resultEqualsValue, FlowScope blindScope) {
439  244 return maybeRestrictName(
440    blindScope, node, type,
441    getRestrictedByTypeOfResult(type, value, resultEqualsValue));
442    }
443   
 
444  142 toggle private FlowScope caseInstanceOf(Node left, Node right, FlowScope blindScope,
445    boolean outcome) {
446  142 JSType leftType = getTypeIfRefinable(left, blindScope);
447  142 if (leftType == null) {
448  60 return blindScope;
449    }
450  82 JSType rightType = right.getJSType();
451  82 ObjectType targetType =
452    typeRegistry.getNativeObjectType(JSTypeNative.UNKNOWN_TYPE);
453  82 if (rightType != null && rightType.isFunctionType()) {
454  82 targetType = rightType.toMaybeFunctionType();
455    }
456  82 Visitor<JSType> visitor;
457  82 if (outcome) {
458  40 visitor = new RestrictByTrueInstanceOfResultVisitor(targetType);
459    } else {
460  42 visitor = new RestrictByFalseInstanceOfResultVisitor(targetType);
461    }
462  82 return maybeRestrictName(
463    blindScope, left, leftType, leftType.visit(visitor));
464    }
465   
466    /**
467    * Given 'property in object', ensures that the object has the property in the
468    * informed scope by defining it as a qualified name if the object type lacks
469    * the property and it's not in the blind scope.
470    * @param object The node of the right-side of the in.
471    * @param propertyName The string of the left-side of the in.
472    */
 
473  2 toggle private FlowScope caseIn(Node object, String propertyName, FlowScope blindScope) {
474  2 JSType jsType = object.getJSType();
475  2 jsType = this.getRestrictedWithoutNull(jsType);
476  2 jsType = this.getRestrictedWithoutUndefined(jsType);
477   
478  2 boolean hasProperty = false;
479  2 ObjectType objectType = ObjectType.cast(jsType);
480  2 if (objectType != null) {
481  2 hasProperty = objectType.hasProperty(propertyName);
482    }
483  2 if (!hasProperty) {
484  2 String qualifiedName = object.getQualifiedName();
485  2 if (qualifiedName != null) {
486  0 String propertyQualifiedName = qualifiedName + "." + propertyName;
487  0 if (blindScope.getSlot(propertyQualifiedName) == null) {
488  0 FlowScope informed = blindScope.createChildFlowScope();
489  0 JSType unknownType = typeRegistry.getNativeType(
490    JSTypeNative.UNKNOWN_TYPE);
491  0 informed.inferQualifiedSlot(
492    object, propertyQualifiedName, unknownType, unknownType);
493  0 return informed;
494    }
495    }
496    }
497  2 return blindScope;
498    }
499   
500    /**
501    * @see SemanticReverseAbstractInterpreter#caseInstanceOf
502    */
 
503    private class RestrictByTrueInstanceOfResultVisitor
504    extends RestrictByTrueTypeOfResultVisitor {
505    private final ObjectType target;
506   
 
507  40 toggle RestrictByTrueInstanceOfResultVisitor(ObjectType target) {
508  40 this.target = target;
509    }
510   
 
511  2 toggle @Override
512    protected JSType caseTopType(JSType type) {
513  2 return applyCommonRestriction(type);
514    }
515   
 
516  9 toggle @Override
517    public JSType caseUnknownType() {
518  9 FunctionType funcTarget = JSType.toMaybeFunctionType(target);
519  9 if (funcTarget != null && funcTarget.hasInstanceType()) {
520  9 return funcTarget.getInstanceType();
521    }
522  0 return getNativeType(UNKNOWN_TYPE);
523    }
524   
 
525  6 toggle @Override
526    public JSType caseObjectType(ObjectType type) {
527  6 return applyCommonRestriction(type);
528    }
529   
 
530  23 toggle @Override
531    public JSType caseUnionType(UnionType type) {
532  23 return applyCommonRestriction(type);
533    }
534   
 
535  0 toggle @Override
536    public JSType caseFunctionType(FunctionType type) {
537  0 return caseObjectType(type);
538    }
539   
 
540  31 toggle private JSType applyCommonRestriction(JSType type) {
541  31 if (target.isUnknownType()) {
542  0 return type;
543    }
544   
545  31 FunctionType funcTarget = target.toMaybeFunctionType();
546  31 if (funcTarget.hasInstanceType()) {
547  31 return type.getGreatestSubtype(funcTarget.getInstanceType());
548    }
549   
550  0 return null;
551    }
552    }
553   
554    /**
555    * @see SemanticReverseAbstractInterpreter#caseInstanceOf
556    */
 
557    private class RestrictByFalseInstanceOfResultVisitor
558    extends RestrictByFalseTypeOfResultVisitor {
559    private final ObjectType target;
560   
 
561  42 toggle RestrictByFalseInstanceOfResultVisitor(ObjectType target) {
562  42 this.target = target;
563    }
564   
 
565  6 toggle @Override
566    public JSType caseObjectType(ObjectType type) {
567  6 if (target.isUnknownType()) {
568  0 return type;
569    }
570   
571  6 FunctionType funcTarget = target.toMaybeFunctionType();
572  6 if (funcTarget.hasInstanceType()) {
573  6 if (type.isSubtype(funcTarget.getInstanceType())) {
574  0 return null;
575    }
576   
577  6 return type;
578    }
579   
580  0 return null;
581    }
582   
 
583  23 toggle @Override
584    public JSType caseUnionType(UnionType type) {
585  23 if (target.isUnknownType()) {
586  0 return type;
587    }
588   
589  23 FunctionType funcTarget = target.toMaybeFunctionType();
590  23 if (funcTarget.hasInstanceType()) {
591  23 return type.getRestrictedUnion(funcTarget.getInstanceType());
592    }
593   
594  0 return null;
595    }
596   
 
597  0 toggle @Override
598    public JSType caseFunctionType(FunctionType type) {
599  0 return caseObjectType(type);
600    }
601    }
602    }